Zum Hauptinhalt springen

Dungeon Generator

Für unser Spiel haben wir entschieden einen Dungeon Generator zu implementieren. Das sorgt für mehr Abwechslung und ist typisch für das Dungeon-Crawler-Genre. Allerdings erfordert das sorgfältige Planung und Beachtung verschiedener Aspekte. Schon bei der Modellierung mussten Räume modular aufgebaut sein, damit sie sich kombinieren lassen. Auch die Platzierung von Gegnern, Truhen und Dekorationen musste flexibel anpassbar bleiben.

DunGen Algorithmus​

Es gibt viele Methoden zur prozeduralen Dungeon Generierung. Zum Beispiel:

  • Binary Space Partitioning (BSP)
  • Cellular Automata
  • Agenten-basierte Algorithmen

Wir haben uns jedoch gegen diese Varianten entschieden. Sie bieten oft weniger Kontrolle über den Raumaufbau und die Dekorationen, zudem wären diese Algorithmen in 3D sehr rechenintensiv. Deshalb fiel die Wahl auf einen modularen, baumbasierten Generator, bei dem wir gezielt festlegen können, wie Räume aufgebaut und verbunden sind.

Module

Bild Quelle: https://gamedevelopment.tutsplus.com/bake-your-own-3d-dungeons-with-procedural-recipes--gamedev-14360t

Regeln für die Generierung​

Es müssen folgende Regeln beachtet werden:

  • Der Dungeon besteht aus einer Menge aus Modulen (Räume) welche miteinander verbunden werden
  • Räume können einen bis vier Ausgänge haben
  • Räume können mit Räumen oder Gängen verbunden werden
  • Ein Dungeon muss einen Start- und Endraum haben

Räume und Connector​

Um Räume miteinander verbinden zu können, haben wir eine Hilfsklasse geschrieben: den Connector. Jeder Ausgang eines Raumes bekommt ein Connector, der festlegt, wie groß die Fläche vom Ausgang ist und ob der Ausgang bereits verbunden ist.


public class Connector : MonoBehavior
{
    public Vector2 size = Vector.one * 4f;
    public bool isConnected = false;
}

Diese Connector-Objekte platzieren wir manuell an die vorgesehenen Ausgänge der Räume. Connector

Algorithmus in Kurzform​

  1. Platziere Startraum
  2. Wähle zufällig ein Raum aus und verbinde dies mit einem der Ausgänge
  3. Falls eine Kollision/Überschneidung mit einem anderen Raum gibt, wähle ein anderen Ausgang aus
  4. Wiederhole Schritt 2 bis alle Räume platziert worden sind
  5. Platziere den Endraum
  6. Platziere Wände an Ausgängen, die nicht mit einem Raum verbunden sind
  7. Platziere Monster und Dekorationen

Dungeon Generierung​

DunGen DunGenTree Die Dungeon-Struktur entspricht einem Baum: Die nummerierten Räume bilden den Pfad zum Endraum. Andere Ausgänge führen entweder zu neuen Zweigen oder werden blockiert.

Dungeon Parametrisierung​

Unser Generator ist so aufgebaut, dass man ihn flexibel erweitern kann. Zum Beispiel indem man die Raumanzahl oder den Verzweigungsgrad anpasst. Mithilfe von Blender können auch neue Räume modelliert und zu den bestehenden Dungeon Generator hinzugefügt werden. Das Testen hat besonders viel Zeit gekostet, da wir anfangs nicht bedacht hatten, wie man Fehler gezielt reproduzieren kann. Da der Dungeon bei jedem Durchlauf zufällig generiert wird, war es schwierig, Bugs zu beheben. Um dieses Problem zu lösen haben wir sogenannte seeds verwenden, um die Zufallszahlen zu steuern. Mit dem gleichen Seed entsteht immer das gleiche Dungeon-Layout. So lassen sich Fehler zuverlässig reproduzieren und beheben.

Aktuell kann man Parameter nur im Unity-Editor setzen. Eine Anpassung zur Laufzeit im Spiel wäre möglich, wurde bisher aber nicht umgesetzt.

DunGenParameters

Einschränkungen​

  • Aktuell erzeugt der Generator keine Zyklen, nur verzweigte Strukturen
  • Kollisionen oder unpassende Platzierungen lassen sich nur teilweise vermeiden. Für spätere Versionen könnten diese Einschränkungen aufgehoben werden, etwa durch eine dynamische Raumskalierung oder verbesserte Kollisionslogik.